#include <stdio.h>
#include <stdlib.h>

typedef struct LinkQueue
{
	//数据
	int elem;
	//指针
	struct LinkQueue *next;
} linkQ;

linkQ *initQ()
{
	linkQ *head_node = (linkQ *)malloc(sizeof(linkQ));
	head_node->elem = 0;
	head_node->next = NULL;
	return head_node;
}

linkQ *enQ(linkQ *rear, int elem)
{
	printf("入队: %d \n", elem);
	//创建新节点
	linkQ *new_node = (linkQ *)malloc(sizeof(linkQ));
	new_node->elem = elem;
	new_node->next = NULL;

	//尾插法插入数据
	//尾指针节点指向入队节点
	rear->next = new_node;

	//尾指针指向新节点
	rear = new_node;

	return rear;
}

linkQ *deQ(linkQ *top, linkQ *rear)
{
	//如果头指针下一个节点为空,那么队列就空了.
	if (top->next == NULL)
	{
		printf("队列为空!\n");
		return rear;
	}

	//出队
	linkQ *out_node = top->next;
	printf("出队 %d \n", out_node->elem);
	top->next = out_node->next;
	if (rear == out_node)
	{
		rear = top;
	}

	free(out_node);
	return rear;
}

int main()
{
	printf("链表实现队列\n");
	//声明头指针和尾指针
	linkQ *top, *rear;
	//初始化链表头节点
	linkQ *head_node = initQ(rear);
	//把头和尾指针指向头节点
	top = rear = head_node;
	rear = enQ(rear, 1);
	rear = enQ(rear, 2);
	rear = enQ(rear, 3);
	rear = enQ(rear, 4);

	rear = deQ(top, rear);
	rear = deQ(top, rear);
	rear = deQ(top, rear);
	rear = deQ(top, rear);
	rear = deQ(top, rear);
	return 0;
}
